Stream ciphers convert a plaintext to a ciphertext one bit at a time. In general, a stream cipher has a keystream generator that outputs a keystream consisting of a series of bits that, for perfect security, vary in value in an unpredictable manner. Each keystream bit is combined using a Boolean exclusive-OR operation (XOR) with an incoming bit of the plaintext, resulting in an output bit of the ciphertext. Thus, an additive stream cipher encrypts a plaintext by bitwise adding a pseudo-randomly generated keystream into the plaintext, modulo two.
For decryption, the ciphertext bits are XORed with an identical keystream to recover the plaintext bits. Accordingly, a stream cipher is ideally suited to encrypting a continuing stream of data, such as the data passing over a network connection between two computers or other network elements. Also, the security of a stream cipher resides in the randomness of the keystream, however, the keystream must be reproducible in identical form at decryption time. Therefore, design of the keystream generator is essential to security and practical operation.
FIG. 1A is a simplified block diagram of a stream cipher. A key K 401 is fed to keystream generator 402, which outputs keystream 410. Plaintext 412 is encrypted by an encryption function 416 based on keystream 410. As a result, ciphertext output 414 is produced.
The keystream generator of such a stream cipher can be described in terms of a state update function and an output function. For example, in FIG. 1A, keystream generator 402 has internal state information 404, a next state function 406 (state update function), and output function 408. The state update function maps the internal state of the keystream generator at one instant to its next value. The output function maps the internal state to a segment of keystream, and the keystream is defined as the concatenation of the values of the output function. Further background information on stream ciphers is provided in B. Schneier, “Applied Cryptography: Protocols, Algorithms and Source Code in C,” 2nd ed. (New York: John Wiley & Sons, 1996).
Block ciphers such as the Data Encryption Standard (DES) are popularly used for encryption of computer communications. However, empirical evidence indicates that stream ciphers are faster than block ciphers at equivalent security levels. For example, in practical evaluation, the stream ciphers RC4 and SEAL have been determined to be significantly faster than any secure block cipher when implemented on general-purpose computer processors. Further, RC4 and SEAL have survived years of scrutiny by cryptanalysts. SEAL is described in U.S. Pat. No. 5,454,039; U.S. Pat. No. 5,675,652; U.S. Pat. No. 5,835,597; Rogaway, P. and Coppersmith, D., “A Software-Optimized Encryption Algorithm”, Proceedings of the 1994 Fast Software Encryption Workshop, Lecture Notes in Computer Science, Volume 809, Springer-Verlag, 1994, pp. 56-63; Rogaway, P. and Copphersmith, D., “A Software-Optimized Encryption Algorithm”, Journal of Cryptology, Volume 11, Number 4, Springer-Verlag, 1998, Pages 273-287, and at the document seal-abstract.html in the directory/˜rogaway/papers/ of the “www.cs” subdomain of the Internet domain ucdavis.edu. Both SEAL and RC4 are discussed in Schneier.
Further, theoretically, a stream cipher is inherently immune to a chosen plaintext attack, and can contain more state information than a block cipher. A block cipher needs to have both encryption and decryption to be secure, and needs to have the avalanche property from the middle to both ends. For example, changing a single bit in the middle of the cipher should change each bit of the input and the output with probability of about ½. Also, the stream cipher has the advantage that its outputs are ordered, while a block cipher must be able to efficiently compute every possible output in any possible order. As a result, for many applications stream ciphers are now clearly preferable over block ciphers.
Unfortunately, many stream ciphers have a significant limitation; most cannot efficiently seek to an arbitrary location in their keystream. In this context, seeking to an arbitrary location in the keystream means generating a segment of keystream that is conceptually located an arbitrary number of bits ahead of that portion of keystream that would be generated by ordinary operation of the keystream in its then-current state. This capability is required for numerous practical applications. For example, in a communications protocol that uses unreliable transport, there is no guarantee that data packets of a particular flow will arrive in order, or arrive at all. Examples of such protocols include Internet Protocol (IP), UDP, and RTP. Such protocols commonly experience loss and reorder of packets in practice. Therefore, for a flow that includes successive packets a, b, and c, a cipher may need to encrypt packet c before it encrypts packet b. A stream cipher can be used to provide privacy for data communicated using such protocols, if the cipher can seek to the proper location in the keystream for packet c based on a sequence number.
Similarly, an encrypted disk partition or file system can use a stream cipher if the cipher supports the seek operation.
These examples do not require the random access capability of a block cipher, in which all inputs are equally simple to compute. Rather, the example applications require the capability to seek into the keystream, with a seek time that is not significant relative to the time required to generate the keystream itself. In this context, “seek” is used in the same sense as used in the POSIX and ANSI C functions for repositioning the offset of a file descriptor.
In one past approach to providing a stream cipher with a seek capability, the state update function is made linear in some field. In this approach, a seek is a composition of linear operations, and therefore is itself linear. This approach is similar to using a block cipher in counter mode, which imposes requirements on the output function that are similar to the requirements on block ciphers.
In an alternative approach, as taken by Rogaway et al. in the design of the SEAL cipher, a special seek function is defined that pseudo-randomly maps an index and a fixed key to an internal state of a keystream generator. Based on this state information, the keystream generator can generate a length of keystream. The keystream for the cipher is defined to be the concatenation of the keystreams generated for each index, with indices in ascending order. Effectively, this approach creates a stream cipher that can seek to some regularly spaced locations in its keystream.
While this approach is satisfactory for many applications, some applications may require the ability to seek to an arbitrary location in the keystream. For example, an encrypted database containing many small records could have this requirement. In addition, the seek function approach adds security requirements. The seek function itself must be secure, and the seek and advance functions must be such that they do not interact in an insecure way.
Based on the foregoing, there is a clear need for an additive stream cipher method that can seek to an arbitrary location in its keystream.
There is a specific need for a stream cipher that provides a keystream seek capability without using a linear state update function, and without a special seek function.
There is also a need to provide such a stream cipher in an embodiment that achieves excellent performance when executed in software implemented for general-purpose computer processors.